// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

func jumpSearch(array []int, key int) int {
	var blockSize = int(math.Sqrt(float64(len(array))))
	var i = 0
	for {
		if array[i] >= key {
			break
		}
		if i > len(array) {
			break
		}
		i += blockSize
	}
	for j := i; j > 0; j-- {
		if array[j] == key {
			return j
		}
	}
	return -1
}

func main() {
	array := []int{1, 2, 6, 5, 88, 66, 77, 69, 76, 99}
	fmt.Println(jumpSearch(array, 77))
}

//$ go run jumpSearch.go
//6
